package main

import (
	"encoding/json"
)

func main() {
	var matrix [][]int
	_ = json.Unmarshal([]byte("[[1,2,3],[4,5,6],[7,8,9]]"), &matrix)
	rotate(matrix)
}

// 289. 生命游戏 https://leetcode.cn/problems/game-of-life/
func gameOfLife(board [][]int) {
	m := len(board)
	n := len(board[0])
	// 遍历
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			aliveNum := gameOfLifeAroundLive(board, i, j)
			if board[i][j] == 1 {
				if aliveNum < 2 || aliveNum > 3 {
					board[i][j] = -1
				}
			} else {
				if aliveNum == 3 {
					board[i][j] = 2
				}
			}
			// 如果是活细胞 判断周围活细胞数量 2 <= x <= 3 to die  1 => -1
			// 如果是死细胞 周围有3个活细胞 0=>2
		}
	}

	// 第三次遍历 -1 => 0  2=>1
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			if board[i][j] == 2 {
				board[i][j] = 1
			} else if board[i][j] == -1 {
				board[i][j] = 0
			}
		}
	}
}

// 判断周围活细胞数量
func gameOfLifeAroundLive(board [][]int, i, j int) int {
	direction := [][]int{
		{-1, -1}, {-1, 0}, {-1, 1},
		{0, -1}, {0, 1},
		{1, -1}, {1, 0}, {1, 1},
	}

	m := len(board)
	n := len(board[0])
	aliveNum := 0
	for _, d := range direction {
		x1 := i + d[0]
		y1 := j + d[1]
		if x1 < 0 || x1 >= m || y1 >= n || y1 < 0 {
			continue //越界了
		}
		if board[x1][y1] == 1 || board[x1][y1] == -1 {
			aliveNum++
		}
		if aliveNum == 4 {
			return 4 //多余4就没必要查询了
		}
	}
	return aliveNum
}

// 73. 矩阵置零 https://leetcode.cn/problems/set-matrix-zeroes
// 用第一行记录当前列是否有0 用第一列记录当前行是否有0 同时要保存第一行第一列是否有0
func setZeroes(matrix [][]int) {
	row := len(matrix)    //多少行
	col := len(matrix[0]) //多少列
	firstRow := false
	firstCol := false

	// 判断首行是否有0 遍历首行每一列
	for i := 0; i < col; i++ {
		if matrix[0][i] == 0 {
			firstRow = true
			break
		}
	}
	// 判断首列是否有0 遍历首列每一行
	for i := 0; i < row; i++ {
		if matrix[i][0] == 0 {
			firstCol = true
			break
		}
	}
	// 从 1-1开始
	for i := 1; i < row; i++ {
		for j := 1; j < col; j++ {
			if matrix[i][j] == 0 {
				matrix[0][j] = 0 //本列有0
				matrix[i][0] = 0 //本行有0
			}
		}
	}
	for i := 1; i < row; i++ {
		for j := 1; j < col; j++ {
			if matrix[i][0] == 0 || matrix[0][j] == 0 {
				matrix[i][j] = 0
			}
		}
	}

	// 处理首行
	if firstRow {
		for i := 0; i < col; i++ {
			matrix[0][i] = 0
		}
	}
	// 处理首列
	if firstCol {
		for i := 0; i < row; i++ {
			matrix[i][0] = 0
		}
	}
}

// 48. 旋转图像 https://leetcode.cn/problems/rotate-image
func rotate(matrix [][]int) {
	n := len(matrix)
	for i := 0; i < n; i++ {
		for j := i; j < n; j++ {
			matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
		}
	}

	for i := 0; i < n; i++ {
		for j := 0; j < n/2; j++ {
			matrix[i][j], matrix[i][n-j-1] = matrix[i][n-j-1], matrix[i][j]
		}
	}
}

// 54. 螺旋矩阵 https://leetcode.cn/problems/spiral-matrix/
func spiralOrder(matrix [][]int) []int {
	u, l := 0, 0
	d := len(matrix) - 1
	r := len(matrix[0]) - 1
	res := []int{}
	for {
		// 水平向右
		for i := l; i <= r; i++ {
			res = append(res, matrix[u][i])
		}
		u++
		if u > d {
			break
		}

		// 垂直向下
		for i := u; i <= d; i++ {
			res = append(res, matrix[i][r])
		}
		r--
		if r < l {
			break
		}

		// 水平向左
		for i := r; i >= l; i-- {
			res = append(res, matrix[d][i])
		}
		d--
		if d < u {
			break
		}

		//垂直向上
		for i := d; i >= u; i-- {
			res = append(res, matrix[i][l])
		}
		l++
		if l > r {
			break
		}
	}
	return res
}

func isValidSudoku(board [][]byte) bool {
	col := [9][9]bool{}      //列
	row := [9][9]bool{}      //行
	block := [3][3][9]bool{} //区域

	for i := 0; i < 9; i++ {
		for j := 0; j < 9; j++ {
			if board[i][j] == '.' {
				continue
			}
			v := board[i][j] - '1'

			if col[i][v] || row[j][v] || block[i/3][j/3][v] {
				return false
			}
			col[i][v] = true
			row[j][v] = true
			block[i/3][j/3][v] = true
		}
	}
	return true
}
